#include "canPartition.h"
bool canPartitionOpt(std::vector<int> &nums) {
    if (nums.size() < 2)
        return false;
    int sums = 0;
    int max_value = 0;
    for (int i = 0; i < nums.size(); i++) {
        sums += nums[i];
        max_value = std::max(nums[i], max_value);
    }
    if (sums & 1)
        return false;
    int half = sums >> 1;
    if (max_value > half)
        return false;
    const int n = nums.size();
    std::vector<std::vector<bool>> dp =
        std::vector<std::vector<bool>>(n, std::vector<bool>(half + 1, false));
    for (int row = 0; row < n; row++) {
        dp[row][0] = true;
    }
    dp[0][nums[0]] = true;
    for (int row = 1; row < n; row++) {
        for (int col = 1; col < half + 1; col++) {
            if (col >= nums[row]) {
                dp[row][col] = dp[row - 1][col - nums[row]] | dp[row - 1][col];
            } else {
                dp[row][col] = dp[row - 1][col];
            }
        }
    }
    return dp[n - 1][half];
}

bool canPartition(std::vector<int> &nums) {

    if (nums.size() < 2)
        return false;
    int sums = 0;
    int max_value = 0;
    for (int i = 0; i < nums.size(); i++) {
        sums += nums[i];
        max_value = std::max(nums[i], max_value);
    }
    if (sums & 1)
        return false;
    int half = sums >> 1;
    if (max_value > half)
        return false;
    const int n = nums.size();
    std::vector<std::vector<bool>> dp =
        std::vector<std::vector<bool>>(2, std::vector<bool>(half + 1, false));
    dp[0][0] = true;
    dp[1][0] = true;
    dp[0][nums[0]] = true;
    for (int row = 1; row < n; row++) {
        for (int col = 0; col < half + 1; col++) {
            if (col >= nums[row])
                dp[row & 1][col] =
                    dp[(row - 1) & 1][col - nums[row]] | dp[(row - 1) & 1][col];
            else {

                dp[row & 1][col] = dp[(row - 1) & 1][col];
            }
        }
    }
    return dp[n & 1][half];
}
